package sort_util

//创建一个一个堆，大根堆 或者小根堆 arr[i]>=arr[2i+1]&& arr[i]>=arr[2i+2]
//堆定元素沉到数组尾部，重新调整结构满足堆定义（反复执行当前操作，直至有序）
func HeapSort[T Signed](list []T) {
	//list := []int64{1, 89, 5, 6, 39, 49, 2, 9, 4, 10}
	//构建大根堆
	length := len(list)
	for i := length/2 - 1; i >= 0; i-- {
		//从第一个非叶节点从下往上，从右到左调整结构
		adjustHeap(list, i, length)
	}
	//调整堆结构+交换堆顶元素和末尾元素
	for j := length - 1; j >= 0; j-- {
		swap(list, 0, j)
		length -= 1
		adjustHeap(list, 0, length)
	}
}
func HeapSortNew[T Signed](list []T) {
	var internalSwap func(list []T, a, b int)
	internalSwap = func(arr []T, a, b int) {
		tmp := arr[a]
		arr[a] = arr[b]
		arr[b] = tmp
	}
	var interAdjustHeap func(list []T, index, length int)
	interAdjustHeap = func(list []T, index, length int) {
		for i := index*2 + 1; i <= length; i *= 2 + 1 {
			if i+1 <= length && list[i+1] > list[i] {
				//如果右子节点>左子节点 则取右子节点
				i++
			}
			if list[i] > list[index] {
				internalSwap(list, index, i)
				index = i //继续判定子节点结构是否满足
			} else {
				break
				//当前节点的左右节点已经满足大根堆
			}
		}
	}
	//构建大根堆
	for i := len(list)<<1 - 1; i >= 0; i-- {
		interAdjustHeap(list, i, len(list)-1)
	}
	//堆调整-sort
	length := len(list) - 1
	for i := length; i >= 0; i-- {
		//头顶节点一次往后交换
		internalSwap(list, 0, length)
		length--
		interAdjustHeap(list, 0, length)
	}
}

//arr[i]>=arr[2i+1]&& arr[i]>=arr[2i+2]
func adjustHeap[T Signed](list []T, index, length int) {
	tmp := list[index]                              //父节点的值                      //选取出当前元素
	for k := index*2 + 1; k < length; k = k*2 + 1 { //从i节点的左子节点开始，也就是2i+1处开始
		if k+1 < length && list[k] <= list[k+1] {
			//左子节点< 又子节点 k指向右子节点
			k++
		}
		if list[k] > tmp { //子节点>父节点 子节点往上提
			list[index] = list[k]
			index = k
		} else {
			break
		}
	}
	list[index] = tmp // 将tmp放到最终位置
}
func swap[T Signed](list []T, a, b int) {
	tmp := list[a]
	list[a] = list[b]
	list[b] = tmp
}

func QuickSort[T Signed](list []T) {
	var internalQuickSort func(list []T, l, r int)
	internalQuickSort = func(list []T, l, r int) {
		if l > r {
			return
		}
		tmpLeft := list[l]
		i := l
		j := r
		for i < j {
			for list[j] >= tmpLeft && i < j {
				//从后往前扫描，找到比基准值小的数据
				j--
			}
			if i < j {
				list[i] = list[j]
				i++
			}
			for list[i] < tmpLeft && i < j {
				//从前往后扫描，找到比基准值大的
				i++
			}
			if i < j {
				list[j] = list[i]
				j--
			}
		}
		list[i] = tmpLeft
		internalQuickSort(list, l, i-1)
		internalQuickSort(list, i+1, r)
	}
	internalQuickSort(list, 0, len(list)-1)

}
func interMergeSort[T Signed](arr []T) []T {
	length := len(arr)
	if length < 2 {
		return arr
	}
	middle := length / 2
	left := arr[0:middle]
	right := arr[middle:]
	return merge(interMergeSort(left), interMergeSort(right))
}
func MergeSort[T Signed](arr []T) {
	sortOut := interMergeSort(arr)
	//下边是 结果整理，不属于排序内容
	for i := range sortOut {
		arr[i] = sortOut[i]
	}
}

func merge[T Signed](left []T, right []T) []T {
	var result []T
	for len(left) != 0 && len(right) != 0 {
		if left[0] <= right[0] {
			result = append(result, left[0])
			left = left[1:]
		} else {
			result = append(result, right[0])
			right = right[1:]
		}
	}

	for len(left) != 0 {
		result = append(result, left[0])
		left = left[1:]
	}

	for len(right) != 0 {
		result = append(result, right[0])
		right = right[1:]
	}

	return result
}

// 1 3 7 5 2
func InsertSort[T Signed](list []T) {
	for i := 1; i < len(list); i++ {
		index := 0
		for list[index] < list[i] && index < i {
			//找到x 之前有序插入位置
			index++
		}
		tmpEle := list[i]
		//元素后移
		for k := i; k >= index; k-- {
			list[k] = list[k-1]
		}
		list[index] = tmpEle
	}
}

// 1 3 7 5 2
func BubbleSort[T Signed](list []T) {
	for i := 0; i < len(list); i++ {
		flag := false
		for k := 0; k < len(list)-1-i; k++ {
			if list[k] >= list[k+1] {
				//交换
				tmp := list[k+1]
				list[k+1] = list[k]
				list[k] = tmp
				flag = true
			}
		}
		if !flag {
			//没有交换 已经有序了
			break
		}
	}
}

// 1 3 7 5 2
func SelectSort[T Signed](list []T) {
	for i := 0; i < len(list); i++ {
		tmpEle := i
		for k := i; k < len(list); k++ {
			if list[tmpEle] < list[k] {
				tmpEle = k
			}
		}
		//J靠换元素
		ele := list[i]
		list[i] = list[tmpEle]
		list[tmpEle] = ele
	}
}
